package de.jadehs.cosima.converters;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.emf.ecore.util.EcoreUtil;
import org.jgrapht.DirectedGraph;

import de.jadehs.cosima.CosimaFactory;
import de.jadehs.cosima.CosimaUtil;
import de.jadehs.cosima.IConverter;
import de.jadehs.cosima.MultiState;
import de.jadehs.cosima.ReadFromTape;
import de.jadehs.cosima.State;
import de.jadehs.cosima.StateType;
import de.jadehs.cosima.StatesRegister;
import de.jadehs.cosima.Transition;
import de.jadehs.cosima.TransitionsTable;

public class NFAToDFAConverter implements
		IConverter<TransitionsTable, TransitionsTable> {
	public static final NFAToDFAConverter INSTANCE = new NFAToDFAConverter();
	public static final boolean CREATE_ERROR_STATES = false;

	public TransitionsTable convert(TransitionsTable f) {
		if (!CosimaUtil.isNFA(f)) {
			return f;
		}

		DirectedGraph<State, Transition> graph = TransitionsTableToDirectedGraphConverter.INSTANCE
				.convert(f);

		TransitionsTable table = CosimaFactory.eINSTANCE
				.createTransitionsTable();
		{
			table.setTape(EcoreUtil.copy(f.getTape()));
			table.setName(f.getName());
			StatesRegister reg = CosimaFactory.eINSTANCE.createStatesRegister();
			table.setStates(reg);
		}

		List<Character> alphabet = CosimaUtil.determineConcreteAlphabet(table);
		Map<String, MultiState> unresolvedStates = new HashMap<String, MultiState>();
		Map<String, MultiState> resolvedStates = new HashMap<String, MultiState>();

		MultiState currentState = CosimaFactory.eINSTANCE.createMultiState();
		{
			State start = CosimaUtil.getStartState(f.getStates());
			currentState.setType(start.getType());
			currentState.setStart(start.isStart());
			currentState.getStates().add(start);
			currentState.setName(CosimaUtil.createConcatName(currentState
					.getStates()));
			resolvedStates.put(currentState.getName(), currentState);
		}

		do {
			for (Character c : alphabet) {
				List<State> states = new ArrayList<State>();

				for (State state : currentState.getStates()) {
					Set<Transition> transitions = graph.outgoingEdgesOf(state);
					for (Transition t : transitions) {
						if (CosimaUtil.evaluateStartCondition(t, c.charValue())) {
							states.add(t.getEnd());
						}
					}
				}

//				if (states.isEmpty() && !CREATE_ERROR_STATES) {
//					continue;
//				}

				String newName = states.isEmpty() ? "ERROR" : CosimaUtil
						.createConcatName(states);
				MultiState state = resolvedStates.get(newName);
				{
					if (state == null) {
						state = unresolvedStates.get(newName);
					}

					if (state == null) {
						state = CosimaFactory.eINSTANCE.createMultiState();
						state.setName(newName);

						if (states.isEmpty()) {
							state.setType(StateType.UNDEF);
						} else {
							StateType type = CosimaUtil.hasFinal(states) ? StateType.END
									: StateType.NORMAL;
							state.setType(type);
							state.getStates().addAll(states);
						}

						unresolvedStates.put(newName, state);
					}
				}

				Transition t = CosimaFactory.eINSTANCE.createTransition();
				{
					t.setStart(currentState);
					t.setEnd(state);
					ReadFromTape read = CosimaFactory.eINSTANCE
							.createReadFromTape();
					read.setSymbol(c);
					t.getStartInstructions().add(read);
					table.getTransitions().add(t);
				}
			}

			Iterator<String> iter = unresolvedStates.keySet().iterator();
			{
				currentState = null;

				while (iter.hasNext()) {
					String key = (String) iter.next();

					if (resolvedStates.containsKey(key)) {
						continue;
					}

					currentState = unresolvedStates.remove(key);
					resolvedStates.put(key, currentState);

					break;
				}
			}
		} while (currentState != null);

		for (Transition t : table.getTransitions()) {
			table.getStates().getStates().add(t.getStart());
			table.getStates().getStates().add(t.getEnd());
		}

		return table;
	}
}
